โคลเป็นคนสูบบุหรี่จัด เขาสูบบุหรี่เกือบสามซองต่อวัน เขาตายด้วยโรคมะเร็งปอดในวันที่ 15 กุมภาพันธ์ ค.ศ. 1965 ระหว่างในช่วงที่เขายังประสบความสำเร็จในอาชีพนักร้องอยู่ หนึ่งวันก่อนเขาตาย เขาได้สัมภาษณ์ออกอากาศผ่านทางวิทยุกล่าวว่า "ผมรู้สึกดีขึ้นกว่าก่อน ผมคิดว่าในที่สุดผมก็จัดการมะเร็งนี่อยู่"

หนังสือชื่อ Chicken Soup for the Soul ฉบับปีค.ศ. 1977 เขียนเรื่องของเขาว่า วันที่เขากำลังจะตายนั้น ภรรยาของโคลชื่อ มาเรีย เกือบพลาดมาดูใจเขาเพราะประสบปัญหากับรถยนต์ แต่ว่านี่เป็นเพียงเรื่องเล่าต่อๆกันมาเท่านั้น

อัลบั้มสุดท้ายของเขาชื่อ L-O-V-E อัดขึ้นในต้นเดือนธันวาคมปี1964 เพียงแค่สองสามวันก่อนที่เขาจะเข้าโรงพยาบาลรับการรักษาโรคมะเร็งปอด และเป็นอัลบั้มที่ปล่อยออกไปก่อนที่เขาจะจากโลกนี้ไป เพลง L-O-V-E นั้นขึ้นเป็นอันดับสี่ของบิลบอร์ดชาร์ตในฤดูใบไม้ผลิปี1965

ต่อมาเพลงที่อัดในปี1957 อย่าง When I Fall In Love ก็ขึ้นเป็นอันดับสี่ใน UKชาร์ตของสหราชอาณาจักร ในปี1987

ในปี1983 คนดูแลจัดเก็บเอกสารของ EMI Electrola Records (ซึ่งเป็นบริษัทแม่ของแคปิต็อล) คนพบเพลงของโคลที่อัดไว้แต่ไม่เคยถูกปล่อยออกมา ซึ่งหนึ่งในนั้นมีเพลงที่ร้องเป็นภาษาญี่ปุ่นและภาษาสเปน ชื่อเพลง Tu Eres Tan Amable แคปิต็อลปล่อยเพลงพวกนี้ออกมาในที่สุดในปีหลังๆในรูปของแผ่นLP ชื่อ Unreleased

โคลได้รับเกีรยติให้มีชื่อขึ้นใน Alabama Music Hall of Fame และ Alabama Jazz Hall of Fame เขาได้รับเกียรติให้ได้รับรางวัล Grammy Lifetime Achievement Award ในปี 1990 และในปี 1997 ก็ได้รับเกียรติให้มีชื่อใน Down Beat Jazz Hall of Fame ในปี 2007 ใน Hit Parade Hall of Fame

ในปี1991 Mosaic Recordsได้ปล่อยอัลบั้ม The Complete Capitol Recordings of the Nat King Cole Trio ซึ่งประกอบไปด้วย ซีดีจำนวน18แผ่น มีเพลงถึง349เพลงด้วยกันในชุด และอัลบั้มพิเศษนี้ยังมีในรูปของแผ่นLPคุณภาพดีจำนวน27แผ่นด้วย

น้องชายคนเล็กสุดของแนทชื่อว่า เฟรดดี้ โคล และลูกสาวของแนท นาตาลี โคล ล้วนดำเนินรอยตามเขาโดยการเป็นนักร้องอาชีพ

ฤดูร้อนปี1991 นาตาลีและบิดาของเธอได้รับความนิยมอย่างไม่ได้คาดหมายเอาไว้ จากการที่เธอนำเสียงของเธอและพ่อมารวมเข้าด้วยกันในเพลง Unforgettable โดยเพลงนี้เป็นส่วนหนึ่งในอัลบั้มของเธอที่มอบให้กับบิดา เพลงและอัลบั้มในชื่อเดียวกันคือ Unforgettable นี้ได้รับรางวัล7รางวัลจาก Grammy Award ในปี 1992